/*
 * @lc app=leetcode.cn id=240 lang=java
 *
 * [240] 搜索二维矩阵 II
 */

// @lc code=start
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length ==0 || matrix[0].length == 0){
            return false;
        }

        int m = matrix.length, n = matrix[0].length;

        int row = 0, col = n - 1;

        while(row < m && col >= 0){
            // 从右上角开始搜索
            if(matrix[row][col] == target){
                return true;
            }else if(matrix[row][col] > target){
                // 如果当前值大于target，说明当前列的值都大于target，所以列数减一
                col--;
            }else{
                // 如果当前值小于target，说明当前行的值都小于target，所以行数加一
                row++;
            }
        }
        return false;
    }
}
// @lc code=end

 